

class CircularQueue:
    """
    Queue implementation using circularly linked list for storage
    """
    class _Node:
        __slots__ = '_element', '_next'

        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        """
        Create empty circular queue
        只需要持有一个尾部节点，它的的next指向head
        """
        self._tail: CircularQueue._Node = None
        self._size = 0

    def __len__(self):
        return self._size

    def __str__(self):
        """

        :return:
        """
        data = []
        if self._tail:
            walk = self._tail._next # 从head 开始遍历
            while (walk != self._tail):
                data.append(walk._element)
                walk = walk._next
            data.append(self._tail._element)
        return str(data)

    def is_empty(self):
        return self._size == 0

    def tail(self):
        if self.is_empty():
            raise Exception("Circular Queue is empty.")
        return self._tail._element

    def first(self):
        if self.is_empty():
            raise Exception("Circular Queue is empty")
        return self._tail._next._element

    def enqueue(self, value):
        """
        Add an element to the tail of the queue
        :param value:
        :return:
        """
        new_node = self._Node(value, None)  # 该节点将是新的tail节点
        if self.is_empty():
            new_node._next = new_node  # init circularly
        else:
            new_node._next = self._tail._next  # 新节点的next指向head
            self._tail._next =new_node  # old tail的next指向新节点
        self._tail =  new_node  # 新节点变成tail
        self._size += 1

    def dequeue(self):
        """
        Delete the head of the queue.
        :return:
        """
        if self.is_empty():
            raise Exception("Circular Queue is empty")

        head: CircularQueue._Node = self._tail._next
        if self._size == 1:
            self._tail = None
        else:
            self._tail._next = head._next
        self._size -= 1
        return head._element

    def rotate(self):
        """Rotate front element to the back of the queue"""
        if self._size > 0:
            self._tail = self._tail._next